package LeetCode.leetcode;

import domain.ListNode;

/**
 * @author: leiwenkang
 * @date: 2020/6/30
 * @time: 21:01
 */
public class Test234回文链表 {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        System.out.println(isPalindrome(head));
    }

    public static boolean isPalindrome(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        //反转slow链表
        ListNode secondNode = reverseListNode(slow);
        ListNode firstNode = head;

        while (secondNode != null) {
            if (secondNode.val != firstNode.val) {
                return false;
            }
            secondNode = secondNode.next;
            firstNode = firstNode.next;
        }

        return true;

    }

    private static ListNode reverseListNode(ListNode head) {
        ListNode pre = null;
        ListNode curr = head;

        while (curr != null) {
            ListNode nxt = curr.next;
            curr.next = pre;
            pre = curr;
            curr = nxt;
        }

        return pre;
    }
}
